On a recent 9 hour drive from my parents house back to college after thanksgiving break, I decided to listen to a podcast that I had put on the backburner for quite a while. And that podcast is called arraycast, it’s a podcast about array programming languages. I know that probably might not sound interesting to most people, and to be honest I didn’t even know if I would enjoy it myself. Who would want to listen to people talk about an “obsolete” and niche programming paradigm that’s so old, it’s most popular language is literally called APL (A Programming Language).
I ended up listening to the podcast for the entire 9 hour drive. And after listening to people talk about this paradigm like it was the greatest thing since the transistor, I knew I had to give it a better try. The last (and only) time that I had used an array language was the 2021 advent of code, where I learned the basics of APL in an afternoon, and got through the first 3.5 days before giving up (my terrible solutions). With AOC right around the corner again (3 days away), I now have the perfect opportunity to try again. But this time, I also want to also write my own interpreter.
The language I chose was K, and the main reason for this was the following quote from episode 41 of arraycast.
Its feature set is small; it’s the most, like, human scale in the sense that a person could just write an implementational language. Like when I started with OK, the legends about k5 were that Arthur Whitney implemented this entire language in about 400 lines of C. So I was like: “all right. well I, John, a normal programmer, ought to be able to write an implementation of this in about 1000 lines of JavaScript”. And I did. I even limited myself to 100 columns which is not something that Arthur does [chuckles]. So you know, like within an order of magnitude of the amount of brilliance that was going into the original thing. It’s human scale, like Forth is human scale; anybody can implement a Forth with a couple of weekends and a little bit of dedication. Anybody could implement a k if they have access to good documentation and test fixtures, which are something that’s still, you know, a little bit lacking. Implementing something like J from scratch would be a much, much bigger project; possible, but very hard and you could make your own implementation of Python with a tremendous amount of difficulty and pain, ’cause it’s a pretty hairy language. But then it’s entire ecosystem? No way! So you know small things that one person could implement have a lot of intrinsic benefits.
After hearing this episode, I knew that I wanted to make my own K to learn array programming. My minimal experience with writing interpreters was a befunge-93 interpreter/debugger that I wrote for a hackathon, so this might be a bit of a challenge.
Before starting, I needed to do three things. The first was choose a dielect of K to base my implementation on. The second was to learn a bit of the language so I could test my interpreter as I made it. And the third was to find documentation I could use to help me in my implementation.
SLIM THIS SECTION DOWN, YOU DONT NEED THE FULL HISTORY OF EVERY FUCkING K VARIANT
All of this info comes from john earnest’s episode of arraycast. also this is cool: https://web.archive.org/web/20210612015246/https://ngn.bitbucket.io/k.html
k1 was an internal like non public version of k that I believe was a Morgan Stanley project.
K2 was the version of that, that became its own commercial product as sort of the nucleus of what KX systems did, the k2 reference manual and the k2 user manual are available online so there’s very detailed documentation on how those are supposed work.
k3 is sort of an incremental refinement of k2.
K4 is the basis of the q programming language. q is implemented in k4. But you can see the k4 implementation of q (it isn’t really documented). It’s just a file that ships with the thing, so you can reverse out how k4 must work in order for q to do what it does.
K5 was an experimental project by Arthur Whitney (creator of K) that was originally intended as being part of kOS, which would be like a freestanding operating system that’s just k as the applications language.
k6 was an incremental refinement of K5, it was just same basic language ideas as k5, but recycled.
And then k7 was another, you know, a big overhaul. It diverged from k6 in a lot of ways, syntactically and semantically, and that was never shipped. it become called Shakti
then they skipped over K8 just because, K9 (you know, dogs) and possible legal troubles with kubernetes.
So K9 is a evolution of k7 (like similar to how k6 was an evolution of K5)
summary: And so k7 and K9 are both radically different languages from k5 and K6. k4 is a meaningful diversion, and there’s a clear through-line of just simpler and more general, from k2 to k3 to k5 to K6.
Year Version 1992 K0 1994 K1 1996 K2 2000 K4 unreleased K5 unreleased K6 2018 K7 (Shakti) doesn’t exist K8 2020 K9 (Shakti)
I decided to choose k6 as the base for my implementation, as it seems to have the most documentation and open source implementations to learn from. Those being oK and ngn/k.
Now that I have chosen a K, it’s time to learn a bit of the langauge.
For that I used the following resources: https://xpqz.github.io/kbook/Introduction.html https://github.com/JohnEarnest/ok/tree/gh-pages/docs https://github.com/razetime/ngn-k-tutorial https://github.com/kparc/kcc
And for implementation, I used the following: https://aplwiki.com/wiki/Implementation_resources https://www.jsoftware.com/help/dictionary/dicte.htm https://mathspp.com/blog/tag:lsbasi-apl#body-wrapper https://www.jsoftware.com/ioj/ioj.htm https://github.com/JohnEarnest/ok/blob/gh-pages/oK.js k3 stuff (kinda useful): http://web.archive.org/web/20060214100753/http://www.kx.com/technical/documents/cki.pdf http://web.archive.org/web/20041022042401/http://www.kx.com/technical/documents/kusrlite.pdf http://web.archive.org/web/20050504070651/http://www.kx.com/technical/documents/kreflite.pdf
note: I know that lots of K implementations (notibly ngn/k) use an extremely terse style of C which I assume originated with Arthur Whitney, and can be seen in his original one page j interpreter. As much as I would love to be able to write my interpreter using the same style, I think that would be a bit outside of both my comfort zone and skill level.
I don’t know how to write an interpreter, and I’m lazy, so I’m just going to skim a couple of short tutorials and see if I can figure out the rest. So if this implementation is horrible, sorry, I don’t know what I’m doing and I’m making it up as I go.
personal notes(on read/write implementation using mmmap): https://news.ycombinator.com/threads?id=ngnk And finally, you shouldn’t really be using read when reading from a large file. Using e.g. mmap is probably a more effective solution, especially if you are reading the file sequentially. https://stackoverflow.com/questions/7222164/mmap-an-entire-large-file aio_read? parens parsing https://chat.stackexchange.com/rooms/52405/conversation/lesson-s1-parenthesis-nesting-level https://chat.stackexchange.com/rooms/52405/conversation/lesson-s3-parsing-expressions-with-parentheses
other links: https://www.nsl.com/
Written: 2022-11-29 Last Updated: 2022-11-29